Теорема о стирании скобок

Пусть $\psi$ — функция стирания скобок в канонической записи: $$\sigma = (i_1 \cdots i_{k_1})(i_{k_1+1} \cdots i_{k_2}) \cdots (i_{k_{s-1}+1} \cdots i_n) \Rightarrow \psi(\sigma) = (i_1, \ldots, i_n)$$ Пример: $\sigma = (4~1~2)(5)(6~3) \Rightarrow \psi(\sigma) = (4, 1, 2, 5, 6, 3)$

Функция стирания скобок — биекция $S_n$ на себя.

* пусть $\pi = (i_1, \ldots, i_n) \in S_n$ * расставим в линейной записи $\pi$ скобки, чтобы получить каноническую запись (некоторой другой перестановки): * $i_1$ принадлежит первому циклу, больше всех элементов в этом цикле и меньше первого элемента следующего цикла * $\Rightarrow$ первый элемент $i'$ второго цикла однозначно определяется как самый левый элемент в линейной записи, больший $i_1$ (а значит, всех предыдущих элементов) * аналогично, первый элемент $i''$ третьего цикла однозначно определяется как самый левый элемент в линейной записи, больший $i'$ (и всех предыдущих) * ... * каноническая запись восстанавливается однозначно $\square$

Элемент, больший всех предыдущих в линейной записи перестановки, называется **префикс-максимумом** В $S_n$ перестановок с $k$ циклами столько же, сколько перестановок с $k$ префикс-максимумами.